package com.ztom.daily.n2022.m4;

/**
 * 字符的最短距离
 * <p>
 * https://leetcode-cn.com/problems/shortest-distance-to-a-character/
 *
 * @author ZhangTao
 */
public class Day19ShortestToChar {

    public int[] shortestToChar(String s, char c) {
        if (s == null || s.length() == 0) {
            return null;
        }

        int n = s.length();
        int[] res = new int[n];
        // 先从左往右遍历, 找到每个位置左边最近的 c
        int t = -n;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == c) {
                t = i;
            }
            res[i] = i - t;
        }
        // 再从右往做遍历, 找到每个位置右边最近的 c, 取最小值
        t = 2 * n;
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == c) {
                t = i;
            }
            res[i] = Math.min(res[i], t - i);
        }
        return res;
    }
}
